package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 200.岛屿数量
 *
 * @program: LeetCode->LeetCode_200
 * @description: 200.岛屿数量
 * @author: cg
 * @create: 2021-09-06 19:10
 **/
public class LeetCode_200 {

    @Test
    public void test200() {
        System.out.println(numIslands(new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}}));
        System.out.println(numIslands(new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}}));
    }

    /**
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     * <p>
     * 示例 1：
     * 输入：grid = [
     * ["1","1","1","1","0"],
     * ["1","1","0","1","0"],
     * ["1","1","0","0","0"],
     * ["0","0","0","0","0"]
     * ]
     * 输出：1
     * <p>
     * 示例 2：
     * 输入：grid = [
     * ["1","1","0","0","0"],
     * ["1","1","0","0","0"],
     * ["0","0","1","0","0"],
     * ["0","0","0","1","1"]
     * ]
     * 输出：3
     * <p>
     * 提示：
     * 1) m == grid.length
     * 2) n == grid[i].length
     * 3) 1 <= m, n <= 300
     * 4) grid[i][j] 的值为 '0' 或 '1'
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        //深度优先解决
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int i, int j) {
        //判断临界
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        //上
        dfs(grid, i - 1, j);
        //下
        dfs(grid, i + 1, j);
        //左
        dfs(grid, i, j - 1);
        //右
        dfs(grid, i, j + 1);
    }
    /*public int numIslands(char[][] grid) {
        //广度优先解决
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    bfs(grid, i, j);
                }
            }
        }
        return res;
    }

    private void bfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';
        Deque<Integer> deque = new ArrayDeque<>();
        // code把坐标转化为一位数字,m为行,n为列
        int n = grid.length, m = grid[0].length, code = i * m + j;
        deque.add(code);
        while (!deque.isEmpty()) {
            code = deque.poll();
            //反转成坐标值(x, y)
            int x = code / m, y = code % m;
            // 上
            if (x > 0 && grid[x - 1][y] == '1') {
                grid[x - 1][y] = '0';
                deque.add((x - 1) * m + y);
            }
            // 下
            if (x < n - 1 && grid[x + 1][y] == '1') {
                grid[x + 1][y] = '0';
                deque.add((x + 1) * m + y);
            }
            // 左
            if (y > 0 && grid[x][y - 1] == '1') {
                grid[x][y - 1] = '0';
                deque.add(x * m + y - 1);
            }
            // 右
            if (y < m - 1 && grid[x][y + 1] == '1') {
                grid[x][y + 1] = '0';
                deque.add(x * m + y + 1);
            }
        }
    }*/

}
